package com.xyj.week01;

/**
 * 已知一个链表有环，找出这个环的起点
 */
public class T2 {


    public static void main(String[] args) {
        //初始化环形链表
        Node node = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node2;
        Node theBegin = getTheBegin(node);
        System.out.println(theBegin);
    }

    /**
     * 快慢指针会相遇  相遇后，快指针走了2k，慢指针走了k，k就是环的长度
     * 这时候假设慢指针离环起点的距离是x 那么从头节点走k-x就是起点
     * 而此时如果慢指针再走k-x也到了起点。
     * @param head 头节点
     * @return 环的起点
     */
    public static Node getTheBegin(Node head){
        Node slow=head;
        Node fast=head;

        while (fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if (fast==slow){
             break;
            }
        }
        while (head!=slow){
            head=head.next;
            slow=slow.next;
        }
        return slow;
    }
}
